﻿namespace Nomo.CoreModule
{
    /// <summary>
    /// 二叉堆。
    /// </summary>
    /// <typeparam name="T">二叉堆中的成员的类型。</typeparam>
    public sealed class BinaryHeap<T> : System.Collections.Generic.IEnumerable<T>
    {
        private readonly bool                                    _isMaxHeap;
        private          T[]                                     _array;
        private          int                                     _size;
        private readonly System.Collections.Generic.IComparer<T> _comparer;
        private          int                                     _version;

        /// <summary>
        /// 初始化 <see cref="BinaryHeap{T}"/> 类的新实例，该实例被指定为最大堆或最小堆，拥有指定的初始容量，并根据指定的比较器来比较成员的大小。
        /// </summary>
        /// <param name="isMaxHeap">如果传入 <see langword="true"/> ，该实例为最大堆；否则为最小堆。</param>
        /// <param name="capacity">初始容量。</param>
        /// <param name="comparer">用于比较成员的大小的比较器。</param>
        /// <exception cref="System.ArgumentOutOfRangeException"><paramref name="capacity"/> 小于 0 .</exception>
        public BinaryHeap(bool isMaxHeap, int capacity = default, System.Collections.Generic.IComparer<T> comparer = default)
        {
            if (capacity < 0)
            {
                throw new System.ArgumentOutOfRangeException(nameof(capacity));
            }
            _isMaxHeap = isMaxHeap;
            _array     = new T[capacity];
            _size      = 0;
            _comparer  = comparer ?? System.Collections.Generic.Comparer<T>.Default;
            _version   = default;
        }

        /// <summary>
        /// 初始化 <see cref="BinaryHeap{T}"/> 类的新实例，该实例被指定为最大堆或最小堆，拥有指定枚举数中的所有成员，并根据指定的比较器来比较成员的大小。
        /// </summary>
        /// <param name="isMaxHeap">如果传入 <see langword="true"/> ，该实例为最大堆；否则为最小堆。</param>
        /// <param name="enumerable">提供初始化此实例的初始成员的枚举数。</param>
        /// <param name="comparer">用于比较成员的大小的比较器。</param>
        /// <exception cref="System.ArgumentNullException"><paramref name="enumerable"/> 为 <see langword="null"/> .</exception>
        /// <exception cref="System.OverflowException"><paramref name="enumerable"/> 中的成员数量超过了 <see cref="int"/> 的最大值。</exception>
        public BinaryHeap(bool isMaxHeap, System.Collections.Generic.IEnumerable<T> enumerable, System.Collections.Generic.IComparer<T> comparer = default)
        {
            if (enumerable == null)
            {
                throw new System.ArgumentNullException(nameof(enumerable));
            }
            _isMaxHeap = isMaxHeap;
            _array     = new T[0];
            _size      = 0;
            _comparer  = comparer ?? System.Collections.Generic.Comparer<T>.Default;
            _version   = default;
            AddRange(enumerable);
            _version = default;
        }

        /// <summary>
        /// 获取 <see cref="BinaryHeap{T}"/> 中的成员数量。
        /// </summary>
        public int Count => _size;

        /// <summary>
        /// 向 <see cref="BinaryHeap{T}"/> 添加一个对象。
        /// </summary>
        /// <param name="t">要添加到 <see cref="BinaryHeap{T}"/> 的对象。</param>
        /// <exception cref="System.OverflowException"><see cref="BinaryHeap{T}"/> 的容量不足以容纳将要添加的对象，需要进行扩容，但新的容量超过了 <see cref="int"/> 的最大值。</exception>
        public void Add(T t)
        {
            var length = _array.Length;
            if (_size == length)
            {
                var len = checked(length * 2 + 1);
                var arr = new T[len];
                System.Array.Copy(_array, 0, arr, 0, length);
                _array = arr;
            }
            _array[_size++] = t;
            ShiftUp(_size - 1);
            ++_version;
        }

        /// <summary>
        /// 向 <see cref="BinaryHeap{T}"/> 添加指定序列包含的所有成员。
        /// </summary>
        /// <param name="enumerable">包含所有要添加到 <see cref="BinaryHeap{T}"/> 的成员的序列。</param>
        /// <exception cref="System.ArgumentNullException"><paramref name="enumerable"/> 为 <see langword="null"/> .</exception>
        /// <exception cref="System.OverflowException"><see cref="BinaryHeap{T}"/> 的容量不足以容纳将要添加的对象，需要进行扩容，但新的容量超过了 <see cref="int"/> 的最大值。</exception>
        public void AddRange(System.Collections.Generic.IEnumerable<T> enumerable)
        {
            if (enumerable == null)
            {
                throw new System.ArgumentNullException(nameof(enumerable));
            }
            foreach (var element in enumerable)
            {
                Add(element);
            }
        }

        /// <summary>
        /// 移除并返回 <see cref="BinaryHeap{T}"/> 中最大或最小的（取决于此二叉堆是最大堆还是最小堆）成员。
        /// </summary>
        /// <returns><see cref="BinaryHeap{T}"/> 中最大或最小的（取决于此二叉堆是最大堆还是最小堆）成员。</returns>
        /// <exception cref="System.InvalidOperationException">二叉堆的成员数为 0 .</exception>
        public T Take()
        {
            if (_size == 0)
            {
                throw new System.InvalidOperationException("二叉堆的成员数为 0 .");
            }
            var t = _array[0];
            _array[0] = _array[--_size];
            ShiftDown(0);
            ++_version;
            return t;
        }

        /// <summary>
        /// 移除 <see cref="BinaryHeap{T}"/> 中的所有成员，并将它们按从大到小或从小到大（取决于此二叉堆是最大堆还是最小堆）的顺序放入一个新数组，最后返回这个新数组。
        /// </summary>
        /// <returns>含有按从大到小或从小到大（取决于此二叉堆是最大堆还是最小堆）的顺序排列的 <see cref="BinaryHeap{T}"/> 中的所有成员的数组。</returns>
        public T[] TakeAll()
        {
            var array = new T[_size];
            var index = 0;
            while (_size > 0)
            {
                array[index++] = Take();
            }
            return array;
        }

        /// <summary>
        /// 返回 <see cref="BinaryHeap{T}"/> 中最大或最小的（取决于此二叉堆是最大堆还是最小堆）成员。
        /// </summary>
        /// <returns><see cref="BinaryHeap{T}"/> 中最大或最小的（取决于此二叉堆是最大堆还是最小堆）成员。</returns>
        /// <exception cref="System.InvalidOperationException">二叉堆的成员数为 0 .</exception>
        public T Peek()
        {
            if (_size == 0)
            {
                throw new System.InvalidOperationException("二叉堆的成员数为 0 .");
            }
            return _array[0];
        }

        /// <summary>
        /// 确定某个对象是否在 <see cref="BinaryHeap{T}"/> 中。
        /// </summary>
        /// <param name="t">要确定是否在 <see cref="BinaryHeap{T}"/> 中的对象。</param>
        /// <returns>如果在 <see cref="BinaryHeap{T}"/> 中找到了 <paramref name="t"/> ，则返回 <see langword="true"/> ；否则返回 <see langword="false"/> .</returns>
        public bool Contains(T t)
        {
            return IndexOf(t) != -1;
        }

        private int IndexOf(T t)
        {
            var equalityComparer = System.Collections.Generic.EqualityComparer<T>.Default;
            for (var i = 0; i < _size; i++)
            {
                if (equalityComparer.Equals(_array[i], t))
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 从 <see cref="BinaryHeap{T}"/> 中移除某个成员。
        /// </summary>
        /// <param name="t">要从 <see cref="BinaryHeap{T}"/> 中移除的对象。</param>
        /// <returns>如果在 <see cref="BinaryHeap{T}"/> 中找到了 <paramref name="t"/> ，则会移除它，并且返回 <see langword="true"/> ；否则返回 <see langword="false"/> .</returns>
        public bool Remove(T t)
        {
            var index = IndexOf(t);
            if (index == -1)
            {
                return false;
            }
            if (index == --_size)
            {
                ++_version;
                return true;
            }
            _array[index] = _array[_size];
            ShiftDown(index);
            ++_version;
            return true;
        }

        /// <summary>
        /// 从 <see cref="BinaryHeap{T}"/> 中移除所有成员。
        /// </summary>
        public void Clear()
        {
            if (_size == 0)
            {
                return;
            }
            System.Array.Clear(_array, 0, _size);
            _size = 0;
            ++_version;
        }

        private void ShiftUp(int index)
        {
            while (index > 0)
            {
                var parentIndex = (index - 1) >> 1;
                var compare     = _comparer.Compare(_array[parentIndex], _array[index]);
                if (_isMaxHeap ? compare >= 0 : compare <= 0)
                {
                    break;
                }
                Swap(index, parentIndex);
                index = parentIndex;
            }
        }

        private void ShiftDown(int index)
        {
            var half = _size >> 1;
            while (index < half)
            {
                var mostIndex      = index;
                var leftChildIndex = (index << 1) + 1;
                var compare        = _comparer.Compare(_array[leftChildIndex], _array[mostIndex]);
                if (_isMaxHeap ? compare > 0 : compare < 0)
                {
                    mostIndex = leftChildIndex;
                }
                var rightChildIndex = leftChildIndex + 1;
                if (rightChildIndex < _size)
                {
                    compare = _comparer.Compare(_array[rightChildIndex], _array[mostIndex]);
                    if (_isMaxHeap ? compare > 0 : compare < 0)
                    {
                        mostIndex = rightChildIndex;
                    }
                }
                if (mostIndex == index)
                {
                    break;
                }
                Swap(index, mostIndex);
                index = mostIndex;
            }
        }

        private void Swap(int index1, int index2)
        {
            if (index1 == index2)
            {
                return;
            }
            var temp = _array[index1];
            _array[index1] = _array[index2];
            _array[index2] = temp;
        }

        /// <summary>
        /// 获取可用于枚举 <see cref="BinaryHeap{T}"/> 的成员的枚举器。
        /// </summary>
        /// <returns>可用于枚举 <see cref="BinaryHeap{T}"/> 的成员的枚举器。</returns>
        public Enumerator GetEnumerator() => new Enumerator(this);

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => new Enumerator(this);

        System.Collections.Generic.IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator() => new Enumerator(this);

        /// <summary>
        /// 用于枚举 <see cref="BinaryHeap{T}"/> 的成员的枚举器。
        /// </summary>
        public struct Enumerator : System.Collections.Generic.IEnumerator<T>
        {
            private readonly BinaryHeap<T> _binaryHeap;
            private readonly int           _version;
            private          T             _currentElement;
            private          int           _index;

            internal Enumerator(BinaryHeap<T> binaryHeap)
            {
                _binaryHeap     = binaryHeap;
                _version        = binaryHeap._version;
                _currentElement = default;
                _index          = -1;
            }

            /// <summary>
            /// 释放此枚举器使用的所有资源。
            /// </summary>
            public void Dispose()
            {
                _index          = -2;
                _currentElement = default;
            }

            /// <summary>
            /// 使枚举器前进到 <see cref="BinaryHeap{T}"/> 下一个成员。
            /// </summary>
            /// <returns>是否成功前进？</returns>
            /// <exception cref="System.InvalidOperationException">在枚举期间修改了 <see cref="BinaryHeap{T}"/> .</exception>
            public bool MoveNext()
            {
                if (_version != _binaryHeap._version)
                {
                    throw new System.InvalidOperationException("在枚举期间修改了二叉堆。");
                }
                if (_index == -2)
                {
                    return false;
                }
                ++_index;
                if (_index == _binaryHeap._size)
                {
                    _index          = -2;
                    _currentElement = default;
                    return false;
                }
                _currentElement = _binaryHeap._array[_index];
                return true;
            }

            /// <summary>
            /// 获取枚举器当前位置的 <see cref="BinaryHeap{T}"/> 的成员。
            /// </summary>
            /// <exception cref="System.InvalidOperationException">枚举器位于 <see cref="BinaryHeap{T}"/> 的第一个成员之前，或最后一个成员之后。</exception>
            public T Current
            {
                get
                {
                    if (_index == -2)
                    {
                        throw new System.InvalidOperationException("枚举器位于二叉堆的第一个成员之前。");
                    }
                    if (_index == -1)
                    {
                        throw new System.InvalidOperationException("枚举器位于二叉堆的最后一个成员之后。");
                    }
                    return _currentElement;
                }
            }

            object System.Collections.IEnumerator.Current
            {
                get
                {
                    if (_index == -2)
                    {
                        throw new System.InvalidOperationException("枚举器位于二叉堆的第一个成员之前。");
                    }
                    if (_index == -1)
                    {
                        throw new System.InvalidOperationException("枚举器位于二叉堆的最后一个成员之后。");
                    }
                    return _currentElement;
                }
            }

            /// <summary>
            /// 重置枚举器。
            /// </summary>
            /// <exception cref="System.InvalidOperationException">在枚举期间修改了 <see cref="BinaryHeap{T}"/> .</exception>
            public void Reset()
            {
                if (_version != _binaryHeap._version)
                {
                    throw new System.InvalidOperationException("在枚举期间修改了二叉堆。");
                }
                _index          = -1;
                _currentElement = default;
            }
        }
    }
}
